#include <dbg.h>
#include <gtest/gtest.h>

using namespace std;

#ifdef SILIYOU
class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        long long res = 0;

        sort(nums.begin(), nums.end());
        dbg(nums);

        for (int i = 0; i < nums.size(); ++i) {
            // <= upper - nums[i] 的 nums[i] 的个数
            auto left =
                upper_bound(nums.begin(), nums.begin() + i, upper - nums[i]);
            dbg(left - nums.begin());

            // < lower - nums[i] 的 nums[i] 的个数
            auto right =
                lower_bound(nums.begin(), nums.begin() + i, lower - nums[i]);
            dbg(right - nums.begin());

            res += distance(right, left);
            dbg(res);
        }
        return res;
    }
};
#endif

class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        long long res = 0;

        sort(nums.begin(), nums.end());
        dbg(nums);

        int n = nums.size();
        int i = n;
        int j = n;
        for (int k = 0; k < n; ++k) {
            while (j > 0 && nums[j - 1] + nums[k] > upper) {
                --j;
            }
            while (i > 0 && nums[i - 1] + nums[k] >= lower) {
                --i;
            }
            res += min(j, k) - min(i, k);
            dbg(i, j, k, res);
        }
        return res;
    }
};

TEST(TEST1_countFairPairs_Test, countFairPairs) {
    Solution solution;

    vector<int> nums = {0, 1, 7, 4, 4, 5};

    int lower = 3;
    int upper = 6;

    long long res = solution.countFairPairs(nums, lower, upper);
    EXPECT_EQ(res, 6);
}

TEST(TEST2_countFairPairs_Test, countFairPairs) {
    Solution solution;

    vector<int> nums = {1, 7, 9, 2, 5};

    int lower = 11;
    int upper = 11;

    long long res = solution.countFairPairs(nums, lower, upper);
    EXPECT_EQ(res, 1);
}

int main(int argc, char** argv) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}